// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License.  You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing,
// software distributed under the License is distributed on an
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied.  See the License for the
// specific language governing permissions and limitations
// under the License.
/// Original is here https://github.com/cerevra/int
/// Distributed under the Boost Software License, Version 1.0.
/// (See at http://www.boost.org/LICENSE_1_0.txt)

// This file is copied from
// https://github.com/ClickHouse/ClickHouse/blob/master/base/base/wide_integer_impl.h
// and modified by Doris
#pragma once

#include <boost/math/special_functions/fpclassify.hpp>
#include <cassert>
#include <cfloat>
#include <cmath>
#include <compare>
#include <limits>
#include <tuple>
#include <type_traits>

#include "common/exception.h"

// NOLINTBEGIN(*)

/// Use same extended double for all platforms
#if (LDBL_MANT_DIG == 64)
#define CONSTEXPR_FROM_DOUBLE constexpr
using FromDoubleIntermediateType = long double;
#else
#include <boost/multiprecision/cpp_bin_float.hpp>
/// `wide_integer_from_builtin` can't be constexpr with non-literal `cpp_bin_float_double_extended`
#define CONSTEXPR_FROM_DOUBLE
using FromDoubleIntermediateType = boost::multiprecision::cpp_bin_float_double_extended;
#endif

namespace CityHash_v1_0_2 {
struct uint128;
}

namespace wide {

template <typename T>
struct IsWideInteger {
    static const constexpr bool value = false;
};

template <size_t Bits, typename Signed>
struct IsWideInteger<wide::integer<Bits, Signed>> {
    static const constexpr bool value = true;
};

template <typename T>
static constexpr bool ArithmeticConcept() noexcept {
    return std::is_arithmetic_v<T> || IsWideInteger<T>::value;
}

template <typename T>
static constexpr bool IntegralConcept() noexcept {
    return std::is_integral_v<T> || IsWideInteger<T>::value;
}

template <typename T>
class IsTupleLike {
    template <typename U>
    static auto check(U* p) -> decltype(std::tuple_size<U>::value, int());
    template <typename>
    static void check(...);

public:
    static constexpr const bool value = !std::is_void<decltype(check<T>(nullptr))>::value;
};

} // namespace wide

namespace std {

// numeric limits
template <size_t Bits, typename Signed>
class numeric_limits<wide::integer<Bits, Signed>> {
public:
    static constexpr bool is_specialized = true;
    static constexpr bool is_signed = is_same<Signed, signed>::value;
    static constexpr bool is_integer = true;
    static constexpr bool is_exact = true;
    static constexpr bool has_infinity = false;
    static constexpr bool has_quiet_NaN = false;
    static constexpr bool has_signaling_NaN = true;
    static constexpr std::float_denorm_style has_denorm = std::denorm_absent;
    static constexpr bool has_denorm_loss = false;
    static constexpr std::float_round_style round_style = std::round_toward_zero;
    static constexpr bool is_iec559 = false;
    static constexpr bool is_bounded = true;
    static constexpr bool is_modulo = true;
    static constexpr int digits = Bits - (is_same<Signed, signed>::value ? 1 : 0);
    static constexpr int digits10 = digits * 0.30103 /*std::log10(2)*/;
    static constexpr int max_digits10 = 0;
    static constexpr int radix = 2;
    static constexpr int min_exponent = 0;
    static constexpr int min_exponent10 = 0;
    static constexpr int max_exponent = 0;
    static constexpr int max_exponent10 = 0;
    static constexpr bool traps = true;
    static constexpr bool tinyness_before = false;

    static constexpr wide::integer<Bits, Signed> min() noexcept {
        if (is_same<Signed, signed>::value) {
            using T = wide::integer<Bits, signed>;
            T res {};
            res.items[T::_impl::big(0)] = std::numeric_limits<
                    typename wide::integer<Bits, Signed>::signed_base_type>::min();
            return res;
        }
        return wide::integer<Bits, Signed>(0);
    }

    static constexpr wide::integer<Bits, Signed> max() noexcept {
        using T = wide::integer<Bits, Signed>;
        T res {};
        res.items[T::_impl::big(0)] =
                is_same<Signed, signed>::value
                        ? std::numeric_limits<
                                  typename wide::integer<Bits, Signed>::signed_base_type>::max()
                        : std::numeric_limits<
                                  typename wide::integer<Bits, Signed>::base_type>::max();
        for (unsigned i = 1; i < wide::integer<Bits, Signed>::_impl::item_count; ++i) {
            res.items[T::_impl::big(i)] =
                    std::numeric_limits<typename wide::integer<Bits, Signed>::base_type>::max();
        }
        return res;
    }

    static constexpr wide::integer<Bits, Signed> lowest() noexcept { return min(); }
    static constexpr wide::integer<Bits, Signed> epsilon() noexcept { return 0; }
    static constexpr wide::integer<Bits, Signed> round_error() noexcept { return 0; }
    static constexpr wide::integer<Bits, Signed> infinity() noexcept { return 0; }
    static constexpr wide::integer<Bits, Signed> quiet_NaN() noexcept { return 0; }
    static constexpr wide::integer<Bits, Signed> signaling_NaN() noexcept { return 0; }
    static constexpr wide::integer<Bits, Signed> denorm_min() noexcept { return 0; }
};

// type traits
template <size_t Bits, typename Signed, size_t Bits2, typename Signed2>
struct common_type<wide::integer<Bits, Signed>, wide::integer<Bits2, Signed2>> {
    using type = std::conditional_t < Bits == Bits2,
          wide::integer<Bits, std::conditional_t<(std::is_same_v<Signed, Signed2> &&
                                                  std::is_same_v<Signed2, signed>),
                                                 signed, unsigned>>,
          std::conditional_t<
                  Bits2<Bits, wide::integer<Bits, Signed>, wide::integer<Bits2, Signed2>>>;
};

template <size_t Bits, typename Signed, typename Arithmetic>
struct common_type<wide::integer<Bits, Signed>, Arithmetic> {
    static_assert(wide::ArithmeticConcept<Arithmetic>());

    using type = std::conditional_t < std::is_floating_point_v<Arithmetic>, Arithmetic,
          std::conditional_t<sizeof(Arithmetic) * 8 < Bits, wide::integer<Bits, Signed>,
                             std::conditional_t<Bits<
                                     sizeof(Arithmetic) * 8, Arithmetic,
                                     std::conditional_t<Bits == sizeof(Arithmetic) * 8 &&
                                                                (std::is_same_v<Signed, signed> ||
                                                                 std::is_signed_v<Arithmetic>),
                                                        Arithmetic, wide::integer<Bits, Signed>>>>>;
};

template <typename Arithmetic, size_t Bits, typename Signed>
struct common_type<Arithmetic, wide::integer<Bits, Signed>>
        : common_type<wide::integer<Bits, Signed>, Arithmetic> {};

} // namespace std

namespace wide {

template <size_t Bits, typename Signed>
struct integer<Bits, Signed>::_impl {
    static constexpr size_t _bits = Bits;
    static constexpr const unsigned byte_count = Bits / 8;
    static constexpr const unsigned item_count = byte_count / sizeof(base_type);
    static constexpr const unsigned base_bits = sizeof(base_type) * 8;

    static_assert(Bits % base_bits == 0);

    /// Simple iteration in both directions
    static constexpr unsigned little(unsigned idx) {
        if constexpr (std::endian::native == std::endian::little) {
            return idx;
        } else {
            return item_count - 1 - idx;
        }
    }
    static constexpr unsigned big(unsigned idx) {
        if constexpr (std::endian::native == std::endian::little) {
            return item_count - 1 - idx;
        } else {
            return idx;
        }
    }
    static constexpr unsigned any(unsigned idx) { return idx; }

    template <class T>
    constexpr static bool is_negative(const T& n) noexcept {
        if constexpr (std::is_signed_v<T>) {
            return n < 0;
        } else {
            return false;
        }
    }

    template <size_t B, class T>
    constexpr static bool is_negative(const integer<B, T>& n) noexcept {
        if constexpr (std::is_same_v<T, signed>) {
            return static_cast<signed_base_type>(n.items[integer<B, T>::_impl::big(0)]) < 0;
        } else {
            return false;
        }
    }

    template <typename T>
    constexpr static auto make_positive(const T& n) noexcept {
        if constexpr (std::is_signed_v<T>) {
            return n < 0 ? -n : n;
        } else {
            return n;
        }
    }

    template <size_t B, class S>
    constexpr static integer<B, S> make_positive(const integer<B, S>& n) noexcept {
        return is_negative(n) ? integer<B, S>(operator_unary_minus(n)) : n;
    }

    template <typename T>
    __attribute__((no_sanitize("undefined"))) constexpr static auto to_Integral(T f) noexcept {
        /// NOTE: this can be called with DB::Decimal, and in this case, result
        /// will be wrong
        if constexpr (std::is_signed_v<T>) {
            return static_cast<int64_t>(f);
        } else {
            return static_cast<uint64_t>(f);
        }
    }

    template <typename Integral>
    constexpr static void wide_integer_from_builtin(integer<Bits, Signed>& self,
                                                    Integral rhs) noexcept {
        if constexpr (std::is_same_v<Integral, __int128> ||
                      std::is_same_v<Integral, unsigned __int128>) {
            self.items[little(0)] = rhs;
            self.items[little(1)] = rhs >> 64;
            if (rhs < 0) {
                for (unsigned i = 2; i < item_count; ++i) {
                    self.items[little(i)] = -1;
                }
                return;
            } else {
                for (unsigned i = 2; i < item_count; ++i) {
                    self.items[little(i)] = 0;
                }
            }
        } else {
            static_assert(sizeof(Integral) <= sizeof(base_type));

            self.items[little(0)] = _impl::to_Integral(rhs);

            if constexpr (std::is_signed_v<Integral>) {
                if (rhs < 0) {
                    for (unsigned i = 1; i < item_count; ++i) {
                        self.items[little(i)] = -1;
                    }
                    return;
                }
            }

            for (unsigned i = 1; i < item_count; ++i) {
                self.items[little(i)] = 0;
            }
        }
    }

    template <typename TupleLike, size_t i = 0>
    constexpr static void wide_integer_from_tuple_like(integer<Bits, Signed>& self,
                                                       const TupleLike& tuple) noexcept {
        if constexpr (i < item_count) {
            if constexpr (i < std::tuple_size_v<TupleLike>) {
                self.items[i] = std::get<i>(tuple);
            } else {
                self.items[i] = 0;
            }
            wide_integer_from_tuple_like<TupleLike, i + 1>(self, tuple);
        }
    }

    template <typename CityHashUInt128 = CityHash_v1_0_2::uint128>
    constexpr static void wide_integer_from_cityhash_uint128(
            integer<Bits, Signed>& self, const CityHashUInt128& value) noexcept {
        static_assert(sizeof(item_count) >= 2);

        if constexpr (std::endian::native == std::endian::little) {
            wide_integer_from_tuple_like(self, std::make_pair(value.low64, value.high64));
        } else {
            wide_integer_from_tuple_like(self, std::make_pair(value.high64, value.low64));
        }
    }

    /**
     * N.B. t is constructed from double, so max(t) = max(double) ~ 2^310
     * the recursive call happens when t / 2^64 > 2^64, so there won't be more than 5 of them.
     *
     * t = a1 * max_int + b1,   a1 > max_int, b1 < max_int
     * a1 = a2 * max_int + b2,  a2 > max_int, b2 < max_int
     * a_(n - 1) = a_n * max_int + b2, a_n <= max_int <- base case.
     */
    template <class T>
    constexpr static void set_multiplier(integer<Bits, Signed>& self, T t) noexcept {
        constexpr uint64_t max_int = std::numeric_limits<uint64_t>::max();
        static_assert(std::is_same_v<T, double> || std::is_same_v<T, FromDoubleIntermediateType>);
        /// Implementation specific behaviour on overflow (if we don't check here, stack overflow will triggered in bigint_cast).
        if constexpr (std::is_same_v<T, double>) {
            if (!std::isfinite(t)) {
                self = 0;
                return;
            }
        } else {
            if (!boost::math::isfinite(t)) {
                self = 0;
                return;
            }
        }

        const T alpha = t / static_cast<T>(max_int);

        /** Here we have to use strict comparison.
          * The max_int is 2^64 - 1.
          * When casted to floating point type, it will be rounded to the closest representable number,
          * which is 2^64.
          * But 2^64 is not representable in uint64_t,
          * so the maximum representable number will be strictly less.
          */
        if (alpha < static_cast<T>(max_int)) {
            self = static_cast<uint64_t>(alpha);
        } else { // max(double) / 2^64 will surely contain less than 52 precision bits, so speed up computations.
            set_multiplier<double>(self, static_cast<double>(alpha));
        }

        self *= max_int;
        self += static_cast<uint64_t>(t - floor(alpha) * static_cast<T>(max_int)); // += b_i
    }

    CONSTEXPR_FROM_DOUBLE static void wide_integer_from_builtin(integer<Bits, Signed>& self,
                                                                double rhs) noexcept {
        constexpr int64_t max_int = std::numeric_limits<int64_t>::max();
        constexpr int64_t min_int = std::numeric_limits<int64_t>::lowest();

        /// There are values in int64 that have more than 53 significant bits (in terms of double
        /// representation). Such values, being promoted to double, are rounded up or down. If they are rounded up,
        /// the result may not fit in 64 bits.
        /// The example of such a number is 9.22337e+18.
        /// As to_Integral does a static_cast to int64_t, it may result in UB.
        /// The necessary check here is that FromDoubleIntermediateType has enough significant (mantissa) bits to store the
        /// int64_t max value precisely.

        if (rhs > static_cast<FromDoubleIntermediateType>(min_int) &&
            rhs < static_cast<FromDoubleIntermediateType>(max_int)) {
            self = static_cast<int64_t>(rhs);
            return;
        }

        const FromDoubleIntermediateType rhs_long_double =
                (static_cast<FromDoubleIntermediateType>(rhs) < 0)
                        ? -static_cast<FromDoubleIntermediateType>(rhs)
                        : rhs;

        set_multiplier(self, rhs_long_double);

        if (rhs < 0) {
            self = -self;
        }
    }

    template <size_t Bits2, typename Signed2>
    constexpr static void wide_integer_from_wide_integer(
            integer<Bits, Signed>& self, const integer<Bits2, Signed2>& rhs) noexcept {
        constexpr const unsigned min_bits = (Bits < Bits2) ? Bits : Bits2;
        constexpr const unsigned to_copy = min_bits / base_bits;

        for (unsigned i = 0; i < to_copy; ++i) {
            self.items[little(i)] = rhs.items[integer<Bits2, Signed2>::_impl::little(i)];
        }

        if constexpr (Bits > Bits2) {
            if constexpr (std::is_signed_v<Signed2>) {
                if (rhs < 0) {
                    for (unsigned i = to_copy; i < item_count; ++i) {
                        self.items[little(i)] = -1;
                    }
                    return;
                }
            }

            for (unsigned i = to_copy; i < item_count; ++i) {
                self.items[little(i)] = 0;
            }
        }
    }

    template <typename T>
    constexpr static bool should_keep_size() {
        return sizeof(T) <= byte_count;
    }

    constexpr static integer<Bits, Signed> shift_left(const integer<Bits, Signed>& rhs,
                                                      unsigned n) noexcept {
        integer<Bits, Signed> lhs;
        unsigned items_shift = n / base_bits;

        if (unsigned bit_shift = n % base_bits) {
            unsigned overflow_shift = base_bits - bit_shift;

            lhs.items[big(0)] = rhs.items[big(items_shift)] << bit_shift;
            for (unsigned i = 1; i < item_count - items_shift; ++i) {
                lhs.items[big(i - 1)] |= rhs.items[big(items_shift + i)] >> overflow_shift;
                lhs.items[big(i)] = rhs.items[big(items_shift + i)] << bit_shift;
            }
        } else {
            for (unsigned i = 0; i < item_count - items_shift; ++i) {
                lhs.items[big(i)] = rhs.items[big(items_shift + i)];
            }
        }

        for (unsigned i = 0; i < items_shift; ++i) {
            lhs.items[little(i)] = 0;
        }
        return lhs;
    }

    constexpr static integer<Bits, Signed> shift_right(const integer<Bits, Signed>& rhs,
                                                       unsigned n) noexcept {
        integer<Bits, Signed> lhs;
        unsigned items_shift = n / base_bits;
        unsigned bit_shift = n % base_bits;

        if (bit_shift) {
            unsigned overflow_shift = base_bits - bit_shift;

            lhs.items[little(0)] = rhs.items[little(items_shift)] >> bit_shift;
            for (unsigned i = 1; i < item_count - items_shift; ++i) {
                lhs.items[little(i - 1)] |= rhs.items[little(items_shift + i)] << overflow_shift;
                lhs.items[little(i)] = rhs.items[little(items_shift + i)] >> bit_shift;
            }
        } else {
            for (unsigned i = 0; i < item_count - items_shift; ++i) {
                lhs.items[little(i)] = rhs.items[little(items_shift + i)];
            }
        }

        if (is_negative(rhs)) {
            if (bit_shift) {
                lhs.items[big(items_shift)] |= std::numeric_limits<base_type>::max()
                                               << (base_bits - bit_shift);
            }

            for (unsigned i = 0; i < items_shift; ++i) {
                lhs.items[big(i)] = std::numeric_limits<base_type>::max();
            }
        } else {
            for (unsigned i = 0; i < items_shift; ++i) {
                lhs.items[big(i)] = 0;
            }
        }

        return lhs;
    }

private:
    template <typename T>
    constexpr static base_type get_item(const T& x, unsigned idx) {
        if constexpr (IsWideInteger<T>::value) {
            if (idx < T::_impl::item_count) {
                return x.items[idx];
            }
            return 0;
        } else {
            if constexpr (sizeof(T) <= sizeof(base_type)) {
                if (little(0) == idx) {
                    return static_cast<base_type>(x);
                }
            } else if (idx * sizeof(base_type) < sizeof(T)) {
                return x >> (idx * base_bits); // & std::numeric_limits<base_type>::max()
            }
            return 0;
        }
    }

    template <typename T>
    constexpr static integer<Bits, Signed> minus(const integer<Bits, Signed>& lhs, T rhs) {
        constexpr const unsigned rhs_items =
                (sizeof(T) > sizeof(base_type)) ? (sizeof(T) / sizeof(base_type)) : 1;
        constexpr const unsigned op_items = (item_count < rhs_items) ? item_count : rhs_items;

        integer<Bits, Signed> res(lhs);
        bool underflows[item_count] = {};

        for (unsigned i = 0; i < op_items; ++i) {
            base_type rhs_item = get_item(rhs, little(i));
            base_type& res_item = res.items[little(i)];

            underflows[i] = res_item < rhs_item;
            res_item -= rhs_item;
        }

        for (unsigned i = 1; i < item_count; ++i) {
            if (underflows[i - 1]) {
                base_type& res_item = res.items[little(i)];
                if (res_item == 0) {
                    underflows[i] = true;
                }
                --res_item;
            }
        }

        return res;
    }

    template <typename T>
    constexpr static integer<Bits, Signed> plus(const integer<Bits, Signed>& lhs, T rhs) {
        constexpr const unsigned rhs_items =
                (sizeof(T) > sizeof(base_type)) ? (sizeof(T) / sizeof(base_type)) : 1;
        constexpr const unsigned op_items = (item_count < rhs_items) ? item_count : rhs_items;

        integer<Bits, Signed> res(lhs);
        bool overflows[item_count] = {};

        for (unsigned i = 0; i < op_items; ++i) {
            base_type rhs_item = get_item(rhs, little(i));
            base_type& res_item = res.items[little(i)];

            res_item += rhs_item;
            overflows[i] = res_item < rhs_item;
        }

        for (unsigned i = 1; i < item_count; ++i) {
            if (overflows[i - 1]) {
                base_type& res_item = res.items[little(i)];
                ++res_item;
                if (res_item == 0) {
                    overflows[i] = true;
                }
            }
        }

        return res;
    }

    template <typename T>
    constexpr static integer<Bits, Signed> multiply(const integer<Bits, Signed>& lhs,
                                                    const T& rhs) {
        if constexpr (Bits == 256 && sizeof(base_type) == 8) {
            /// @sa https://github.com/abseil/abseil-cpp/blob/master/absl/numeric/int128.h
            using HalfType = unsigned __int128;

            HalfType a01 = (HalfType(lhs.items[little(1)]) << 64) + lhs.items[little(0)];
            HalfType a23 = (HalfType(lhs.items[little(3)]) << 64) + lhs.items[little(2)];
            HalfType a0 = lhs.items[little(0)];
            HalfType a1 = lhs.items[little(1)];

            HalfType b01 = rhs;
            uint64_t b0 = b01;
            uint64_t b1 = 0;
            HalfType b23 = 0;
            if constexpr (sizeof(T) > 8) {
                b1 = b01 >> 64;
            }
            if constexpr (sizeof(T) > 16) {
                b23 = (HalfType(rhs.items[little(3)]) << 64) + rhs.items[little(2)];
            }

            HalfType r23 = a23 * b01 + a01 * b23 + a1 * b1;
            HalfType r01 = a0 * b0;
            HalfType r12 = (r01 >> 64) + (r23 << 64);
            HalfType r12_x = a1 * b0;

            integer<Bits, Signed> res;
            res.items[little(0)] = r01;
            res.items[little(3)] = r23 >> 64;

            if constexpr (sizeof(T) > 8) {
                HalfType r12_y = a0 * b1;
                r12_x += r12_y;
                if (r12_x < r12_y) {
                    ++res.items[little(3)];
                }
            }

            r12 += r12_x;
            if (r12 < r12_x) {
                ++res.items[little(3)];
            }

            res.items[little(1)] = r12;
            res.items[little(2)] = r12 >> 64;
            return res;
        } else if constexpr (Bits == 128 && sizeof(base_type) == 8) {
            using CompilerUInt128 = unsigned __int128;
            CompilerUInt128 a =
                    (CompilerUInt128(lhs.items[little(1)]) << 64) +
                    lhs.items[little(
                            0)]; // NOLINT(clang-analyzer-core.UndefinedBinaryOperatorResult)
            CompilerUInt128 b =
                    (CompilerUInt128(rhs.items[little(1)]) << 64) +
                    rhs.items[little(
                            0)]; // NOLINT(clang-analyzer-core.UndefinedBinaryOperatorResult)
            CompilerUInt128 c = a * b;
            integer<Bits, Signed> res;
            res.items[little(0)] = c;
            res.items[little(1)] = c >> 64;
            return res;
        } else {
            integer<Bits, Signed> res {};
#if 1
            integer<Bits, Signed> lhs2 = plus(lhs, shift_left(lhs, 1));
            integer<Bits, Signed> lhs3 = plus(lhs2, shift_left(lhs, 2));
#endif
            for (unsigned i = 0; i < item_count; ++i) {
                base_type rhs_item = get_item(rhs, little(i));
                unsigned pos = i * base_bits;

                while (rhs_item) {
#if 1 /// optimization
                    if ((rhs_item & 0x7) == 0x7) {
                        res = plus(res, shift_left(lhs3, pos));
                        rhs_item >>= 3;
                        pos += 3;
                        continue;
                    }

                    if ((rhs_item & 0x3) == 0x3) {
                        res = plus(res, shift_left(lhs2, pos));
                        rhs_item >>= 2;
                        pos += 2;
                        continue;
                    }
#endif
                    if (rhs_item & 1) {
                        res = plus(res, shift_left(lhs, pos));
                    }

                    rhs_item >>= 1;
                    ++pos;
                }
            }

            return res;
        }
    }

public:
    constexpr static integer<Bits, Signed> operator_unary_tilda(
            const integer<Bits, Signed>& lhs) noexcept {
        integer<Bits, Signed> res;

        for (unsigned i = 0; i < item_count; ++i) {
            res.items[any(i)] = ~lhs.items[any(i)];
        }
        return res;
    }

    constexpr static integer<Bits, Signed> operator_unary_minus(
            const integer<Bits, Signed>& lhs) noexcept(std::is_same_v<Signed, unsigned>) {
        return plus(operator_unary_tilda(lhs), 1);
    }

    template <typename T>
    constexpr static auto operator_plus(const integer<Bits, Signed>& lhs,
                                        const T& rhs) noexcept(std::is_same_v<Signed, unsigned>) {
        if constexpr (should_keep_size<T>()) {
            if (is_negative(rhs)) {
                return minus(lhs, -rhs);
            } else {
                return plus(lhs, rhs);
            }
        } else {
            static_assert(IsWideInteger<T>::value);
            return std::common_type_t<integer<Bits, Signed>, integer<T::_impl::_bits, Signed>>::
                    _impl::operator_plus(integer<T::_impl::_bits, Signed>(lhs), rhs);
        }
    }

    template <typename T>
    constexpr static auto operator_minus(const integer<Bits, Signed>& lhs,
                                         const T& rhs) noexcept(std::is_same_v<Signed, unsigned>) {
        if constexpr (should_keep_size<T>()) {
            if (is_negative(rhs)) {
                return plus(lhs, -rhs);
            } else {
                return minus(lhs, rhs);
            }
        } else {
            static_assert(IsWideInteger<T>::value);
            return std::common_type_t<integer<Bits, Signed>, integer<T::_impl::_bits, Signed>>::
                    _impl::operator_minus(integer<T::_impl::_bits, Signed>(lhs), rhs);
        }
    }

    template <typename T>
    constexpr static auto operator_star(const integer<Bits, Signed>& lhs, const T& rhs) {
        if constexpr (should_keep_size<T>()) {
            integer<Bits, Signed> res;

            if constexpr (std::is_signed_v<Signed>) {
                res = multiply((is_negative(lhs) ? make_positive(lhs) : lhs),
                               (is_negative(rhs) ? make_positive(rhs) : rhs));
            } else {
                res = multiply(lhs, (is_negative(rhs) ? make_positive(rhs) : rhs));
            }

            if (std::is_same_v<Signed, signed> && is_negative(lhs) != is_negative(rhs)) {
                res = operator_unary_minus(res);
            }

            return res;
        } else {
            static_assert(IsWideInteger<T>::value);
            return std::common_type_t<integer<Bits, Signed>, T>::_impl::operator_star(T(lhs), rhs);
        }
    }

    template <typename T>
    constexpr static bool operator_greater(const integer<Bits, Signed>& lhs,
                                           const T& rhs) noexcept {
        if constexpr (should_keep_size<T>()) {
            if (std::numeric_limits<T>::is_signed && (is_negative(lhs) != is_negative(rhs))) {
                return is_negative(rhs);
            }

            integer<Bits, Signed> t = rhs;
            for (unsigned i = 0; i < item_count; ++i) {
                base_type rhs_item = get_item(t, big(i));

                if (lhs.items[big(i)] != rhs_item) {
                    return lhs.items[big(i)] > rhs_item;
                }
            }

            return false;
        } else {
            static_assert(IsWideInteger<T>::value);
            return std::common_type_t<integer<Bits, Signed>, T>::_impl::operator_greater(T(lhs),
                                                                                         rhs);
        }
    }

    template <typename T>
    constexpr static bool operator_less(const integer<Bits, Signed>& lhs, const T& rhs) noexcept {
        if constexpr (should_keep_size<T>()) {
            if (std::numeric_limits<T>::is_signed && (is_negative(lhs) != is_negative(rhs))) {
                return is_negative(lhs);
            }

            integer<Bits, Signed> t = rhs;
            for (unsigned i = 0; i < item_count; ++i) {
                base_type rhs_item = get_item(t, big(i));

                if (lhs.items[big(i)] != rhs_item) {
                    return lhs.items[big(i)] < rhs_item;
                }
            }

            return false;
        } else {
            static_assert(IsWideInteger<T>::value);
            return std::common_type_t<integer<Bits, Signed>, T>::_impl::operator_less(T(lhs), rhs);
        }
    }

    template <typename T>
    constexpr static bool operator_eq(const integer<Bits, Signed>& lhs, const T& rhs) noexcept {
        if constexpr (should_keep_size<T>()) {
            integer<Bits, Signed> t = rhs;
            for (unsigned i = 0; i < item_count; ++i) {
                base_type rhs_item = get_item(t, any(i));

                if (lhs.items[any(i)] != rhs_item) {
                    return false;
                }
            }

            return true;
        } else {
            static_assert(IsWideInteger<T>::value);
            return std::common_type_t<integer<Bits, Signed>, T>::_impl::operator_eq(T(lhs), rhs);
        }
    }

    template <typename T>
    constexpr static auto operator_pipe(const integer<Bits, Signed>& lhs, const T& rhs) noexcept {
        if constexpr (should_keep_size<T>()) {
            integer<Bits, Signed> res;

            for (unsigned i = 0; i < item_count; ++i) {
                res.items[little(i)] = lhs.items[little(i)] | get_item(rhs, little(i));
            }
            return res;
        } else {
            static_assert(IsWideInteger<T>::value);
            return std::common_type_t<integer<Bits, Signed>, T>::_impl::operator_pipe(T(lhs), rhs);
        }
    }

    template <typename T>
    constexpr static auto operator_amp(const integer<Bits, Signed>& lhs, const T& rhs) noexcept {
        if constexpr (should_keep_size<T>()) {
            integer<Bits, Signed> res;

            for (unsigned i = 0; i < item_count; ++i) {
                res.items[little(i)] = lhs.items[little(i)] & get_item(rhs, little(i));
            }
            return res;
        } else {
            static_assert(IsWideInteger<T>::value);
            return std::common_type_t<integer<Bits, Signed>, T>::_impl::operator_amp(T(lhs), rhs);
        }
    }

    template <typename T>
    constexpr static bool is_zero(const T& x) {
        bool is_zero = true;
        for (auto item : x.items) {
            if (item != 0) {
                is_zero = false;
                break;
            }
        }
        return is_zero;
    }

    /// returns quotient as result and remainder in numerator.
    template <size_t Bits2>
    constexpr static integer<Bits2, unsigned> divide(integer<Bits2, unsigned>& numerator,
                                                     integer<Bits2, unsigned> denominator) {
        static_assert(std::is_unsigned_v<Signed>);

        if constexpr (Bits == 128 && sizeof(base_type) == 8) {
            using CompilerUInt128 = unsigned __int128;

            CompilerUInt128 a =
                    (CompilerUInt128(numerator.items[little(1)]) << 64) +
                    numerator.items[little(
                            0)]; // NOLINT(clang-analyzer-core.UndefinedBinaryOperatorResult)
            CompilerUInt128 b =
                    (CompilerUInt128(denominator.items[little(1)]) << 64) +
                    denominator.items[little(
                            0)];       // NOLINT(clang-analyzer-core.UndefinedBinaryOperatorResult)
            CompilerUInt128 c = a / b; // NOLINT

            integer<Bits, Signed> res;
            res.items[little(0)] = c;
            res.items[little(1)] = c >> 64;

            CompilerUInt128 remainder = a - b * c;
            numerator.items[little(0)] = remainder;
            numerator.items[little(1)] = remainder >> 64;

            return res;
        }

        if (is_zero(denominator)) {
            throw doris::Exception(doris::ErrorCode::INVALID_ARGUMENT, "Division by zero");
        }

        integer<Bits2, unsigned> x = 1;
        integer<Bits2, unsigned> quotient = 0;

        while (!operator_greater(denominator, numerator) &&
               is_zero(operator_amp(shift_right(denominator, Bits2 - 1), 1))) {
            x = shift_left(x, 1);
            denominator = shift_left(denominator, 1);
        }

        while (!is_zero(x)) {
            if (!operator_greater(denominator, numerator)) {
                numerator = operator_minus(numerator, denominator);
                quotient = operator_pipe(quotient, x);
            }

            x = shift_right(x, 1);
            denominator = shift_right(denominator, 1);
        }

        return quotient;
    }

    template <typename T>
    constexpr static auto operator_slash(const integer<Bits, Signed>& lhs, const T& rhs) {
        if constexpr (should_keep_size<T>()) {
            integer<Bits, unsigned> numerator = make_positive(lhs);
            integer<Bits, unsigned> denominator = make_positive(integer<Bits, Signed>(rhs));
            integer<Bits, unsigned> quotient =
                    integer<Bits, unsigned>::_impl::divide(numerator, std::move(denominator));

            if (std::is_same_v<Signed, signed> && is_negative(rhs) != is_negative(lhs))
                quotient = operator_unary_minus(quotient);
            return quotient;
        } else {
            static_assert(IsWideInteger<T>::value);
            return std::common_type_t<integer<Bits, Signed>,
                                      integer<T::_impl::_bits, Signed>>::operator_slash(T(lhs),
                                                                                        rhs);
        }
    }

    template <typename T>
    constexpr static auto operator_percent(const integer<Bits, Signed>& lhs, const T& rhs) {
        if constexpr (should_keep_size<T>()) {
            integer<Bits, unsigned> remainder = make_positive(lhs);
            integer<Bits, unsigned> denominator = make_positive(integer<Bits, Signed>(rhs));
            integer<Bits, unsigned>::_impl::divide(remainder, std::move(denominator));

            if (std::is_same_v<Signed, signed> && is_negative(lhs)) {
                remainder = operator_unary_minus(remainder);
            }
            return remainder;
        } else {
            static_assert(IsWideInteger<T>::value);
            return std::common_type_t<integer<Bits, Signed>,
                                      integer<T::_impl::_bits, Signed>>::operator_percent(T(lhs),
                                                                                          rhs);
        }
    }

    // ^
    template <typename T>
    constexpr static auto operator_circumflex(const integer<Bits, Signed>& lhs,
                                              const T& rhs) noexcept {
        if constexpr (should_keep_size<T>()) {
            integer<Bits, Signed> t(rhs);
            integer<Bits, Signed> res = lhs;

            for (unsigned i = 0; i < item_count; ++i) {
                res.items[any(i)] ^= t.items[any(i)];
            }
            return res;
        } else {
            static_assert(IsWideInteger<T>::value);
            return T::operator_circumflex(T(lhs), rhs);
        }
    }

    constexpr static integer<Bits, Signed> from_str(const char* c) {
        integer<Bits, Signed> res = 0;

        bool is_neg = std::is_same_v<Signed, signed> && *c == '-';
        if (is_neg) {
            ++c;
        }

        if (*c == '0' && (*(c + 1) == 'x' || *(c + 1) == 'X')) { // hex
            ++c;
            ++c;
            while (*c) {
                if (*c >= '0' && *c <= '9') {
                    res = multiply(res, 16U);
                    res = plus(res, *c - '0');
                    ++c;
                } else if (*c >= 'a' && *c <= 'f') {
                    res = multiply(res, 16U);
                    res = plus(res, *c - 'a' + 10U);
                    ++c;
                } else if (*c >= 'A' &&
                           *c <= 'F') { // tolower must be used, but it is not constexpr
                    res = multiply(res, 16U);
                    res = plus(res, *c - 'A' + 10U);
                    ++c;
                } else {
                    throw doris::Exception(doris::ErrorCode::INVALID_ARGUMENT, "Invalid char from");
                }
            }
        } else { // dec
            while (*c) {
                if (*c < '0' || *c > '9') {
                    throw doris::Exception(doris::ErrorCode::INVALID_ARGUMENT, "Invalid char from");
                }

                res = multiply(res, 10U);
                res = plus(res, *c - '0');
                ++c;
            }
        }

        if (is_neg) {
            res = operator_unary_minus(res);
        }

        return res;
    }
};

// Members

template <size_t Bits, typename Signed>
template <typename T>
constexpr integer<Bits, Signed>::integer(T rhs) noexcept : items {} {
    if constexpr (IsWideInteger<T>::value) {
        _impl::wide_integer_from_wide_integer(*this, rhs);
    } else if constexpr (IsTupleLike<T>::value) {
        _impl::wide_integer_from_tuple_like(*this, rhs);
    } else if constexpr (std::is_same_v<std::remove_cvref_t<T>, CityHash_v1_0_2::uint128>) {
        _impl::wide_integer_from_cityhash_uint128(*this, rhs);
    } else {
        _impl::wide_integer_from_builtin(*this, rhs);
    }
}

template <size_t Bits, typename Signed>
template <typename T>
constexpr integer<Bits, Signed>::integer(std::initializer_list<T> il) noexcept : items {} {
    if (il.size() == 1) {
        if constexpr (IsWideInteger<T>::value) {
            _impl::wide_integer_from_wide_integer(*this, *il.begin());
        } else if constexpr (IsTupleLike<T>::value) {
            _impl::wide_integer_from_tuple_like(*this, *il.begin());
        } else if constexpr (std::is_same_v<std::remove_cvref_t<T>, CityHash_v1_0_2::uint128>) {
            _impl::wide_integer_from_cityhash_uint128(*this, *il.begin());
        } else {
            _impl::wide_integer_from_builtin(*this, *il.begin());
        }
    } else if (il.size() == 0) {
        _impl::wide_integer_from_builtin(*this, 0);
    } else {
        auto it = il.begin();
        for (unsigned i = 0; i < _impl::item_count; ++i) {
            if (it < il.end()) {
                items[_impl::little(i)] = *it;
                ++it;
            } else {
                items[_impl::little(i)] = 0;
            }
        }
    }
}

template <size_t Bits, typename Signed>
template <size_t Bits2, typename Signed2>
constexpr integer<Bits, Signed>& integer<Bits, Signed>::operator=(
        const integer<Bits2, Signed2>& rhs) noexcept {
    _impl::wide_integer_from_wide_integer(*this, rhs);
    return *this;
}

template <size_t Bits, typename Signed>
template <typename T>
constexpr integer<Bits, Signed>& integer<Bits, Signed>::operator=(T rhs) noexcept {
    if constexpr (IsTupleLike<T>::value) {
        _impl::wide_integer_from_tuple_like(*this, rhs);
    } else if constexpr (std::is_same_v<std::remove_cvref_t<T>, CityHash_v1_0_2::uint128>) {
        _impl::wide_integer_from_cityhash_uint128(*this, rhs);
    } else {
        _impl::wide_integer_from_builtin(*this, rhs);
    }
    return *this;
}

template <size_t Bits, typename Signed>
template <typename T>
constexpr integer<Bits, Signed>& integer<Bits, Signed>::operator*=(const T& rhs) {
    *this = *this * rhs;
    return *this;
}

template <size_t Bits, typename Signed>
template <typename T>
constexpr integer<Bits, Signed>& integer<Bits, Signed>::operator/=(const T& rhs) {
    *this = *this / rhs;
    return *this;
}

template <size_t Bits, typename Signed>
template <typename T>
constexpr integer<Bits, Signed>& integer<Bits, Signed>::operator+=(const T& rhs) noexcept(
        std::is_same_v<Signed, unsigned>) {
    *this = *this + rhs;
    return *this;
}

template <size_t Bits, typename Signed>
template <typename T>
constexpr integer<Bits, Signed>& integer<Bits, Signed>::operator-=(const T& rhs) noexcept(
        std::is_same_v<Signed, unsigned>) {
    *this = *this - rhs;
    return *this;
}

template <size_t Bits, typename Signed>
template <typename T>
constexpr integer<Bits, Signed>& integer<Bits, Signed>::operator%=(const T& rhs) {
    *this = *this % rhs;
    return *this;
}

template <size_t Bits, typename Signed>
template <typename T>
constexpr integer<Bits, Signed>& integer<Bits, Signed>::operator&=(const T& rhs) noexcept {
    *this = *this & rhs;
    return *this;
}

template <size_t Bits, typename Signed>
template <typename T>
constexpr integer<Bits, Signed>& integer<Bits, Signed>::operator|=(const T& rhs) noexcept {
    *this = *this | rhs;
    return *this;
}

template <size_t Bits, typename Signed>
template <typename T>
constexpr integer<Bits, Signed>& integer<Bits, Signed>::operator^=(const T& rhs) noexcept {
    *this = *this ^ rhs;
    return *this;
}

template <size_t Bits, typename Signed>
constexpr integer<Bits, Signed>& integer<Bits, Signed>::operator<<=(int n) noexcept {
    if (static_cast<size_t>(n) >= Bits) {
        *this = 0;
    } else if (n > 0) {
        *this = _impl::shift_left(*this, n);
    }
    return *this;
}

template <size_t Bits, typename Signed>
constexpr integer<Bits, Signed>& integer<Bits, Signed>::operator>>=(int n) noexcept {
    if (static_cast<size_t>(n) >= Bits) {
        if (_impl::is_negative(*this)) {
            *this = -1;
        } else {
            *this = 0;
        }
    } else if (n > 0) {
        *this = _impl::shift_right(*this, n);
    }
    return *this;
}

template <size_t Bits, typename Signed>
constexpr integer<Bits, Signed>& integer<Bits, Signed>::operator++() noexcept(
        std::is_same_v<Signed, unsigned>) {
    *this = _impl::operator_plus(*this, 1);
    return *this;
}

template <size_t Bits, typename Signed>
constexpr integer<Bits, Signed> integer<Bits, Signed>::operator++(int) noexcept(
        std::is_same_v<Signed, unsigned>) {
    auto tmp = *this;
    *this = _impl::operator_plus(*this, 1);
    return tmp;
}

template <size_t Bits, typename Signed>
constexpr integer<Bits, Signed>& integer<Bits, Signed>::operator--() noexcept(
        std::is_same_v<Signed, unsigned>) {
    *this = _impl::operator_minus(*this, 1);
    return *this;
}

template <size_t Bits, typename Signed>
constexpr integer<Bits, Signed> integer<Bits, Signed>::operator--(int) noexcept(
        std::is_same_v<Signed, unsigned>) {
    auto tmp = *this;
    *this = _impl::operator_minus(*this, 1);
    return tmp;
}

template <size_t Bits, typename Signed>
constexpr integer<Bits, Signed>::operator bool() const noexcept {
    return !_impl::operator_eq(*this, 0);
}

template <size_t Bits, typename Signed>
template <class T, class>
constexpr integer<Bits, Signed>::operator T() const noexcept {
    static_assert(std::numeric_limits<T>::is_integer);

    /// NOTE: memcpy will suffice, but unfortunately, this function is constexpr.

    using UnsignedT = std::make_unsigned_t<T>;

    UnsignedT res {};
    for (unsigned i = 0;
         i < _impl::item_count && i < (sizeof(T) + sizeof(base_type) - 1) / sizeof(base_type);
         ++i) {
        res += UnsignedT(items[_impl::little(i)])
               << (sizeof(base_type) * 8 *
                   i); // NOLINT(clang-analyzer-core.UndefinedBinaryOperatorResult)
    }

    return res;
}

template <size_t Bits, typename Signed>
constexpr integer<Bits, Signed>::operator long double() const noexcept {
    if (_impl::operator_eq(*this, 0)) {
        return 0;
    }

    integer<Bits, Signed> tmp = *this;
    if (_impl::is_negative(*this)) {
        tmp = -tmp;
    }

    long double res = 0;
    for (unsigned i = 0; i < _impl::item_count; ++i) {
        long double t = res;
        res *= static_cast<long double>(std::numeric_limits<base_type>::max());
        res += t;
        res += tmp.items[_impl::big(i)];
    }

    if (_impl::is_negative(*this)) {
        res = -res;
    }

    return res;
}

template <size_t Bits, typename Signed>
constexpr integer<Bits, Signed>::operator double() const noexcept {
    return static_cast<double>(static_cast<long double>(*this));
}

template <size_t Bits, typename Signed>
constexpr integer<Bits, Signed>::operator float() const noexcept {
    return static_cast<float>(static_cast<long double>(*this));
}

// Unary operators
template <size_t Bits, typename Signed>
constexpr integer<Bits, Signed> operator~(const integer<Bits, Signed>& lhs) noexcept {
    return integer<Bits, Signed>::_impl::operator_unary_tilda(lhs);
}

template <size_t Bits, typename Signed>
constexpr integer<Bits, Signed> operator-(const integer<Bits, Signed>& lhs) noexcept(
        std::is_same_v<Signed, unsigned>) {
    return integer<Bits, Signed>::_impl::operator_unary_minus(lhs);
}

template <size_t Bits, typename Signed>
constexpr integer<Bits, Signed> operator+(const integer<Bits, Signed>& lhs) noexcept(
        std::is_same_v<Signed, unsigned>) {
    return lhs;
}

#define CT(x)                                                                      \
    std::common_type_t<std::decay_t<decltype(rhs)>, std::decay_t<decltype(lhs)>> { \
        x                                                                          \
    }

// Binary operators
template <size_t Bits, typename Signed, size_t Bits2, typename Signed2>
std::common_type_t<integer<Bits, Signed>, integer<Bits2, Signed2>> constexpr operator*(
        const integer<Bits, Signed>& lhs, const integer<Bits2, Signed2>& rhs) {
    return std::common_type_t<integer<Bits, Signed>, integer<Bits2, Signed2>>::_impl::operator_star(
            lhs, rhs);
}

template <typename Arithmetic, typename Arithmetic2, class>
std::common_type_t<Arithmetic, Arithmetic2> constexpr operator*(const Arithmetic& lhs,
                                                                const Arithmetic2& rhs) {
    return CT(lhs) * CT(rhs);
}

template <size_t Bits, typename Signed, size_t Bits2, typename Signed2>
std::common_type_t<integer<Bits, Signed>, integer<Bits2, Signed2>> constexpr operator/(
        const integer<Bits, Signed>& lhs, const integer<Bits2, Signed2>& rhs) {
    return std::common_type_t<integer<Bits, Signed>,
                              integer<Bits2, Signed2>>::_impl::operator_slash(lhs, rhs);
}
template <typename Arithmetic, typename Arithmetic2, class>
std::common_type_t<Arithmetic, Arithmetic2> constexpr operator/(const Arithmetic& lhs,
                                                                const Arithmetic2& rhs) {
    return CT(lhs) / CT(rhs);
}

template <size_t Bits, typename Signed, size_t Bits2, typename Signed2>
std::common_type_t<integer<Bits, Signed>, integer<Bits2, Signed2>> constexpr operator+(
        const integer<Bits, Signed>& lhs, const integer<Bits2, Signed2>& rhs) {
    return std::common_type_t<integer<Bits, Signed>, integer<Bits2, Signed2>>::_impl::operator_plus(
            lhs, rhs);
}
template <typename Arithmetic, typename Arithmetic2, class>
std::common_type_t<Arithmetic, Arithmetic2> constexpr operator+(const Arithmetic& lhs,
                                                                const Arithmetic2& rhs) {
    return CT(lhs) + CT(rhs);
}

template <size_t Bits, typename Signed, size_t Bits2, typename Signed2>
std::common_type_t<integer<Bits, Signed>, integer<Bits2, Signed2>> constexpr operator-(
        const integer<Bits, Signed>& lhs, const integer<Bits2, Signed2>& rhs) {
    return std::common_type_t<integer<Bits, Signed>,
                              integer<Bits2, Signed2>>::_impl::operator_minus(lhs, rhs);
}
template <typename Arithmetic, typename Arithmetic2, class>
std::common_type_t<Arithmetic, Arithmetic2> constexpr operator-(const Arithmetic& lhs,
                                                                const Arithmetic2& rhs) {
    return CT(lhs) - CT(rhs);
}

template <size_t Bits, typename Signed, size_t Bits2, typename Signed2>
std::common_type_t<integer<Bits, Signed>, integer<Bits2, Signed2>> constexpr operator%(
        const integer<Bits, Signed>& lhs, const integer<Bits2, Signed2>& rhs) {
    return std::common_type_t<integer<Bits, Signed>,
                              integer<Bits2, Signed2>>::_impl::operator_percent(lhs, rhs);
}
template <typename Integral, typename Integral2, class>
std::common_type_t<Integral, Integral2> constexpr operator%(const Integral& lhs,
                                                            const Integral2& rhs) {
    return CT(lhs) % CT(rhs);
}

template <size_t Bits, typename Signed, size_t Bits2, typename Signed2>
std::common_type_t<integer<Bits, Signed>, integer<Bits2, Signed2>> constexpr operator&(
        const integer<Bits, Signed>& lhs, const integer<Bits2, Signed2>& rhs) {
    return std::common_type_t<integer<Bits, Signed>, integer<Bits2, Signed2>>::_impl::operator_amp(
            lhs, rhs);
}
template <typename Integral, typename Integral2, class>
std::common_type_t<Integral, Integral2> constexpr operator&(const Integral& lhs,
                                                            const Integral2& rhs) {
    return CT(lhs) & CT(rhs);
}

template <size_t Bits, typename Signed, size_t Bits2, typename Signed2>
std::common_type_t<integer<Bits, Signed>, integer<Bits2, Signed2>> constexpr operator|(
        const integer<Bits, Signed>& lhs, const integer<Bits2, Signed2>& rhs) {
    return std::common_type_t<integer<Bits, Signed>, integer<Bits2, Signed2>>::_impl::operator_pipe(
            lhs, rhs);
}
template <typename Integral, typename Integral2, class>
std::common_type_t<Integral, Integral2> constexpr operator|(const Integral& lhs,
                                                            const Integral2& rhs) {
    return CT(lhs) | CT(rhs);
}

template <size_t Bits, typename Signed, size_t Bits2, typename Signed2>
std::common_type_t<integer<Bits, Signed>, integer<Bits2, Signed2>> constexpr operator^(
        const integer<Bits, Signed>& lhs, const integer<Bits2, Signed2>& rhs) {
    return std::common_type_t<integer<Bits, Signed>,
                              integer<Bits2, Signed2>>::_impl::operator_circumflex(lhs, rhs);
}
template <typename Integral, typename Integral2, class>
std::common_type_t<Integral, Integral2> constexpr operator^(const Integral& lhs,
                                                            const Integral2& rhs) {
    return CT(lhs) ^ CT(rhs);
}

template <size_t Bits, typename Signed>
constexpr integer<Bits, Signed> operator<<(const integer<Bits, Signed>& lhs, int n) noexcept {
    if (static_cast<size_t>(n) >= Bits) {
        return integer<Bits, Signed>(0);
    }
    if (n <= 0) {
        return lhs;
    }
    return integer<Bits, Signed>::_impl::shift_left(lhs, n);
}
template <size_t Bits, typename Signed>
constexpr integer<Bits, Signed> operator>>(const integer<Bits, Signed>& lhs, int n) noexcept {
    if (static_cast<size_t>(n) >= Bits) {
        return integer<Bits, Signed>(0);
    }
    if (n <= 0) {
        return lhs;
    }
    return integer<Bits, Signed>::_impl::shift_right(lhs, n);
}

template <size_t Bits, typename Signed, size_t Bits2, typename Signed2>
constexpr bool operator<(const integer<Bits, Signed>& lhs, const integer<Bits2, Signed2>& rhs) {
    return std::common_type_t<integer<Bits, Signed>, integer<Bits2, Signed2>>::_impl::operator_less(
            lhs, rhs);
}
template <typename Arithmetic, typename Arithmetic2, class>
constexpr bool operator<(const Arithmetic& lhs, const Arithmetic2& rhs) {
    return CT(lhs) < CT(rhs);
}

template <size_t Bits, typename Signed, size_t Bits2, typename Signed2>
constexpr bool operator>(const integer<Bits, Signed>& lhs, const integer<Bits2, Signed2>& rhs) {
    return std::common_type_t<integer<Bits, Signed>,
                              integer<Bits2, Signed2>>::_impl::operator_greater(lhs, rhs);
}
template <typename Arithmetic, typename Arithmetic2, class>
constexpr bool operator>(const Arithmetic& lhs, const Arithmetic2& rhs) {
    return CT(lhs) > CT(rhs);
}

template <size_t Bits, typename Signed, size_t Bits2, typename Signed2>
constexpr bool operator<=(const integer<Bits, Signed>& lhs, const integer<Bits2, Signed2>& rhs) {
    return std::common_type_t<integer<Bits, Signed>, integer<Bits2, Signed2>>::_impl::operator_less(
                   lhs, rhs) ||
           std::common_type_t<integer<Bits, Signed>, integer<Bits2, Signed2>>::_impl::operator_eq(
                   lhs, rhs);
}
template <typename Arithmetic, typename Arithmetic2, class>
constexpr bool operator<=(const Arithmetic& lhs, const Arithmetic2& rhs) {
    return CT(lhs) <= CT(rhs);
}

template <size_t Bits, typename Signed, size_t Bits2, typename Signed2>
constexpr bool operator>=(const integer<Bits, Signed>& lhs, const integer<Bits2, Signed2>& rhs) {
    return std::common_type_t<integer<Bits, Signed>,
                              integer<Bits2, Signed2>>::_impl::operator_greater(lhs, rhs) ||
           std::common_type_t<integer<Bits, Signed>, integer<Bits2, Signed2>>::_impl::operator_eq(
                   lhs, rhs);
}
template <typename Arithmetic, typename Arithmetic2, class>
constexpr bool operator>=(const Arithmetic& lhs, const Arithmetic2& rhs) {
    return CT(lhs) >= CT(rhs);
}

template <size_t Bits, typename Signed, size_t Bits2, typename Signed2>
constexpr bool operator==(const integer<Bits, Signed>& lhs, const integer<Bits2, Signed2>& rhs) {
    return std::common_type_t<integer<Bits, Signed>, integer<Bits2, Signed2>>::_impl::operator_eq(
            lhs, rhs);
}
template <typename Arithmetic, typename Arithmetic2, class>
constexpr bool operator==(const Arithmetic& lhs, const Arithmetic2& rhs) {
    return CT(lhs) == CT(rhs);
}

template <size_t Bits, typename Signed, size_t Bits2, typename Signed2>
constexpr bool operator!=(const integer<Bits, Signed>& lhs, const integer<Bits2, Signed2>& rhs) {
    return !std::common_type_t<integer<Bits, Signed>, integer<Bits2, Signed2>>::_impl::operator_eq(
            lhs, rhs);
}
template <typename Arithmetic, typename Arithmetic2, class>
constexpr bool operator!=(const Arithmetic& lhs, const Arithmetic2& rhs) {
    return CT(lhs) != CT(rhs);
}

template <size_t Bits, typename Signed, size_t Bits2, typename Signed2>
constexpr auto operator<=>(const integer<Bits, Signed>& lhs, const integer<Bits2, Signed2>& rhs) {
    return (lhs == rhs ? std::strong_ordering::equal
                       : (lhs > rhs ? std::strong_ordering::greater : std::strong_ordering::less));
}

template <typename Arithmetic, typename Arithmetic2, class>
constexpr auto operator<=>(const Arithmetic& rhs, const Arithmetic2& lhs) {
    return (lhs == rhs ? std::strong_ordering::equal
                       : (lhs > rhs ? std::strong_ordering::greater : std::strong_ordering::less));
}

#undef CT

} // namespace wide

namespace std {

template <size_t Bits, typename Signed>
struct hash<wide::integer<Bits, Signed>> {
    std::size_t operator()(const wide::integer<Bits, Signed>& lhs) const {
        static_assert(Bits % (sizeof(size_t) * 8) == 0);

        const auto* ptr = reinterpret_cast<const size_t*>(lhs.items);
        unsigned count = Bits / (sizeof(size_t) * 8);

        size_t res = 0;
        for (unsigned i = 0; i < count; ++i) {
            res ^= ptr[i];
        }
        return res;
    }
};

} // namespace std

// NOLINTEND(*)
